\input{euler.tex}

\newcommand{\given}{\,|\,}

\begin{document}

\problem[302]{Strong Achilles Numbers}

A positive integer $n$ is \emph{powerful} if $p^2$ is a divisor of $n$ for every prime factor $p$ in $n$. 

A positive integer $n$ is a \emph{perfect power} if $n$ can be expressed as a power of another positive integer. 

A positive integer $n$ is an \emph{Achilles number} if $n$ is powerful but not a perfect power. For example, 864 and 1800 are Achilles numbers: $864 = 2^5 \times 3^3$ and $1800 = 2^3 \times 3^2 \times 5^2$.

We shall call a positive integer $S$ a Strong Achilles number if both $S$ and $\varphi(S)$ are Achilles numbers, where $\varphi$ is Euler's totient function. For example, 864 is a Strong Achilles number: $\varphi(864) = 288 = 2^5 \times 3^2$. However, 1800 isn't a Strong Achilles number, because $\varphi(1800) = 480 = 2^5 \times 3^1 \times 5^1$. 

There are 7 Strong Achilles numbers below $10^4$ and 656 below $10^8$. 

How many Strong Achilles numbers are there below $10^{18}$? 

\solution

We first formalize the definition of Achilles numbers. For convenience, we select the first $M$ prime numbers $(p_1, \ldots, p_M)$, and write the prime factorization of an integer $n$ as
\[
n = p_1^{k_1} \cdots p_M^{k_M} ,
\]
where $k_i \ge 0$. Then $n$ is an Achilles number if and only if $k_i \ne 1$ and $\gcd(k_1,\ldots,k_M)=1$. Note that here we define $\gcd(0,a)=a$ for $a \ge 0$.

The totient function of $n$ is
\[
\varphi(n) = \prod_{k_i > 0} (p_i-1)p_i^{k_i-1} .
\]
This value can itself be factorized into a product of the first $M$ prime factors as
\[
\varphi(n) = p_1^{l_1} \cdots p_M^{l_M} ,
\]
where $l_i \ge 0$. In order to make $\varphi(n)$ an Achilles number, we must have $l_i \ne 1$ and $\gcd(l_1,\ldots,l_M)=1$.

To find a Strong Achilles number $n$, we start with the largest prime factor of $n$, $p_M$. Obviously there are no $(p_i-1)$ that contains the factor $p_M$. So $l_M=k_M-1$. Hence $k_M \ge 3$. Note also that an Achilles number must contain at least two prime factors, the smallest being 2. Therefore $n \ge 2^2 \times p_M^3$.

We solve the problem recursively. Let $S_m(n',L_m)$ be the number of Strong Achilles numbers $n \le N$ of the form
\[
n = \left( \prod_{i=1}^m p_i^{k_i} \right) n' ,
\]
where
\[
n' = \prod_{i=m+1}^M p_i^{k_i}
\]
is the partial product of $n$ over the prime factors after $m$, and 
\[
L_m = \prod_{i=1}^m p_i^{l_i}
\]
is the partial factorization of $\varphi(n')$ over the first $m$ prime factors. In order for $n$ to be a Strong Achilles number, we require that 
\[
k_i \ge 0, k_i \ne 1, \text{ and } k_i \ne 2 \text{ if } l_i=0
\]
and $\gcd(k_1,\ldots,k_M)=1, \gcd(l_1,\ldots,l_M)=1$.

We write $S_m(n', L_m)$ as follows:
\[
S_m(n', L_m) = 
\sum_{i}
\sum_{k_i}
S_{i-1}\left( p_i^{k_i} n', (p_i-1)L_m \right) .
\]
That is, we enumerate each $i,k_i$ where $p_i^{k_i}$ is the largest prime factor of $n$ over the first $m$ primes.

Now we need to provide a good range for admissible $i$ and $k_i$ to ensure that $n \le N$. First suppose $i$ is given. Obviously we require $k_i \ge 2$. In addition, if $l_i = 0$, we also require $k_i \ge 3$. Also we require that $p_i^{k_i} n' \le n \le N$, so $k_i \le \log_{p_i} (N/n')$.

Furthermore, suppose $q$ is the largest prime factor of $(p_i-1)$ whose power is one. In order to make $\varphi(n)$ powerful, $n$ must contain another $p_j^{k_j}$ such that either $p_j=q$ or $(p_j-1)$ contains the factor $q$. In either case, $p_j^{k_j} \ge q^2$. Hence we can improve the upper bound of $k_i$ to $\log_{p_i} N/(q^2n')$. Note that if no such $q$ exists, we set $q = 1$.

Next, we provide a range for admissible $i$ where $p_i$ is assumed to be the largest prime factor of $n$ over the first $m$ primes. Obviously, if there exists $j \le m$ where $l_j=1$, then $i \ge j$ because we must put $p_j$ into $n$. Thus the lower bound of $i$ is $\max \, \{j \given l_j=1, j \le m\}$, or 1 if no such $j$ exists. The upper bound of $i$ is the maximum of
\[
\{ i \given p_i^3 n' \le N, l_i = 0 \}
\]
and 
\[
\{ i \given p_i^2 n' \le N, l_i > 0 \} .
\]

The solution to the problem is $S_M(1, 1)$, where $p_M \le (N/4)^{1/3}$.

% The algorithm is outlined as follows. We maintain two vectors $(k_1,\ldots,k_m)$ and $(l_1,\ldots,l_m)$, such that $p_m \le (N/4)^{1/3}$, to store the powers of the prime factors of $n$ and $\varphi(n)$. We then enumerate each possible power from $k_m$ to $k_1$ backward. 

% Step 1. Let $m$ be the largest index such that $p_m \le (N/4)^{1/3}$. Let $n'=1$ be the partial product of prime factors after $p_m$. Let $U=N$ be the upper bound of product of the first $m$ prime factors.

% Step 2. Find the largest admissible prime $p_i$, $i \le m$, that can possibly be a factor of $n$. This is the largest $i$ such that $l_i=0$ and $p_i^3 n' \le N$, or $l_i > 0$ and $p_i^2 n' \le N$.

% Step 3. Factorize $(p_i-1)$ and update $(l_1,\ldots,l_m)$. Let $p_j$ be the largest prime such that $j<m$ and $l_j=1$. Then let lower bound $L=p_j^2$. If no such prime exists, let $LB=1$.

% Step 4. Let $k_i=3$ if $l_i=0$; otherwise let $k_i=2$. While $p_i^{k_i} n' \le N$, run Step 2 recursively by setting $m = i-1$.

% Step 5. Check whether $\gcd(k_1,\ldots,k_m)=1$ and $\gcd(l_1,\ldots,l_m)$. If they are, then $n$ is a Strong Achilles number.

% Step 6. Repeat from Step 2.

Some additional minor optimizations include: 

1. Pre-compute the value of $\gcd(a,b)$ for $0 \le a,b \le 63$. This makes future calls to $\gcd$ a constant time operation.

2. Pre-compute the value of $p_i^3$. This saves expensive and messy integer cube root calls when finding the upper bound of $i$.

\complexity

Time complexity: $\BigO\left((\ln N)^{N^{1/3} \ln N}\right)$. During the recursive call to $S_m$, the last level corresponds to a powerful number, and the depth to that last level is equal to the number of prime factors in that number. The time complexity is roughly proportional to the total number of prime factors of all powerful numbers below $N$. This is of the order $\BigO\left((\ln N)^{N^{1/3} \ln N}\right)$.

Space complexity: $\BigO(N^{1/3}/\ln N)$. It takes $\BigO(N^{1/3}/\ln N)$ to store the candidate prime factors. The recursion level (which determines the stack space) is up to the maximum number of prime factors whose product is below $N$, which is below $\log_2 N$.

\answer

1170060

\seealso

Problem 342: The totient of a square is a cube.

\reference

http://en.wikipedia.org/wiki/Achilles\_number

http://en.wikipedia.org/wiki/Euler's\_totient\_function

\end{document} 